/*
#Copyright (c) 2013, Philippe Bordron <philippe.bordron@gmail.com>
#
# This file is part of SIPPER.
#
# DCC is free software: you can redistribute it and/or modify
# it under the terms of the GNU LESSER GENERAL PUBLIC LICENSE as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# DCC is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU LESSER GENERAL PUBLIC LICENSE for more details.
#
# You should have received a copy of the GNU LESSER GENERAL PUBLIC LICENSE
# along with SIPPER.  If not, see <http://www.gnu.org/licenses/>
*/
package combi.graph;

import java.util.*;


public class PrefixTree<E> extends PrefixTreeNode<E>{

	protected int numberOfLeaves; // identification of the node in the tree
	
	/**
	 * Create an empty PrefixTree
	 */
	public PrefixTree()
	{
		super(null, null);
		successors =  new HashMap<E,PrefixTreeNode<E>>();
		numberOfLeaves = 0;
	}
	
	/**
	 *  Get ????
	 * @return
	 */
	public Collection<PrefixTreeNode<E>> getNodes()
	{
		return successors.values();
	}

	/**
	 * Add a sequence in the prefix tree
	 * @param seq
	 * @return the deviation node.
	 */
	public PrefixTreeNode<E> addSequence(List<E> seq)
	{
		ListIterator<E> it = seq.listIterator();
		numberOfLeaves++;
		return addSequence(it);
	}

	/**
	 * remove a sequence in the prefixe tree
	 * @param seq
	 * @return
	 */
	public boolean removeSequence(List<E> seq)
	{
		ListIterator<E> it = seq.listIterator();
		numberOfLeaves--;
		return removeSequence(it);
	}

	/**
	 * Get the deviation node of the sequence seq in the prefix tree
	 * @param seq
	 * @return
	 */
	public PrefixTreeNode<E> getDeviationNode(List<E> seq)
	{
		return getDeviationNode(seq.listIterator());
	}

	/**
	 * Return a representation of the prefix tree in a String
	 */
	public String toString()
	{
		String res = "";
		for(PrefixTreeNode<E> n : successors.values())
		{
			res = res + n.toString(0);
		}
		return res;
	}

	/**
	 * Return the prefix tree into paths
	 */
	public List<List<E>> toPaths()
	{
		List<List<E>> result = new LinkedList<List<E>>();
		for (PrefixTreeNode<E> n : successors.values())
		{
			result.addAll(n.toPaths());
		}
		return result;
	}
	
	/**
	 * Get the root of the prefixe tree
	 * @return a PrefixNode
	 */
	public PrefixTreeNode<E> getRoot()
	{
		return this;
	}

	/**
	 * Test if the prefix tree is empty
	 * @return true if the prefix tree is empty (false else)
	 */
	public boolean isEmpty()
	{
		return successors.isEmpty();
	}
	
	/**
	 * Get the number of leafs in the prefix tree (i.e. the number of prefixes)
	 * @return the number of leafs
	 */
	public int getNumberOfLeafs()
	{
		return numberOfLeaves;
	}
	
	
	public static void main(String[] args) {
		PrefixTree<Integer> t = new PrefixTree<Integer>();
		List<Integer> l;
		Integer[] l1 = new Integer[]{1,2,5,3,6};
		Integer[] l2 = new Integer[]{1,2,3,3,6};
		Integer[] l3 = new Integer[]{1,2,3,6,6};
		Integer[] l4 = new Integer[]{1,3,3,6,6};
		Integer[] l5 = new Integer[]{5,6,8,9,1,2};
		l = Arrays.asList(l1);
		PrefixTreeNode<Integer> dev = t.addSequence(l);
		l = Arrays.asList(l2);
		t.addSequence(l);
		l = Arrays.asList(l3);
		t.addSequence(l);
		l = Arrays.asList(l4);
		t.addSequence(l);
		l = Arrays.asList(l5);
		t.addSequence(l);
		System.out.println(t);
		t.removeSequence(l);
		System.out.println("----------------");
		System.out.println(t);

		Integer[] s = new Integer[]{1,4,3,6,6};
		l = Arrays.asList(s);
		System.out.println("----------------");
		System.out.println(dev.getVal());
		System.out.println(t.getDeviationNode(l));
		System.out.println(t.toPaths());
		t.clear();

		System.out.println("----------------");
		System.out.println(t.toPaths());
	}


}
